/*
 * @Descripttion: 
 * @version: 
 * @Author: lily
 * @Date: 2021-03-29 13:18:44
 * @LastEditors: lily
 * @LastEditTime: 2021-04-03 16:14:20
 */
/*
 * @lc app=leetcode.cn id=10 lang=javascript
 *
 * [10] 正则表达式匹配
 */

// @lc code=start
/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
//  思路：动态规划
//  dp[i][j]表示s[i]和p[j]是否匹配 
//  s[i] p[j]分别增加一个空格作为初始值 即首行、首列为初始值 
//  1 => p[j] !== s[i]                 意思是：当前不匹配  false
//  2 => p[j] === s[i] || p[j] === '.' 
//       2.1 => dp[i-1][j-1] === true  意思是：当前匹配，前面也匹配  true
//       2.2 => dp[i-1][j-1] === true  意思是：当前匹配，前面不匹配  false
//  3 => p[j] === "*"  
//       3.1 => dp[i][j-2] === true    意思是：没有 字母* 的前面字串就已匹配 true
//       3.2 => dp[i][j-2] === false   意思是：没有 字母* 的前面字串没有匹配
//              3.2.2 => p[j-1] !== s[i]                     意思是 *前的字母 与s[i]不匹配 加了字母也没用  false
//              3.2.1 => p[j-1] === s[i] || p[j-1] === '.'   意思是 *前的字母 与s[i]匹配
//                       dp[i-1][j] === false                意思是 增加*前的字母后 当前匹配，去掉s[i]后不匹配 false
//                       dp[i-1][j] === true                 意思是 增加*前的字母后 当前匹配，去掉s[i]后也匹配 true

//  复杂度：O(mn)  O(mn)  m、n为s、p的长度


var isMatch = function (s, p) {
    // https://leetcode-cn.com/problems/regular-expression-matching/solution/shi-pin-tu-jie-dong-tai-gui-hua-zheng-ze-biao-da-s/
    let sn = s.length + 1, pn = p.length + 1
    let dp = Array.from(new Array(sn), () => new Array(pn).fill(0))

    // 初始化表
    for (let i = 0; i < sn; i++) {
        //  空格与空格匹配一致，其余字母匹配空格不一致
        dp[i][0] = i === 0 ? true : false
    }
    for (let j = 1; j < pn; j++) {
        // 如果是* 同行前两格是否一致 意思是 *前字母不存在就已经匹配 那当前一定匹配 否则不匹配
        dp[0][j] = p[j - 1] === "*" ? dp[0][j - 2] : false
    }

    for (let i = 1; i < sn; i++) {
        for (let j = 1; j < pn; j++) {
            // 如果是* 
            // 1.看dp[i][j - 2] 即 某*不存在时是否匹配, 整串=dp[i][j - 2]
            // 2.看 当前s 与 *前的字母是否匹配(包括.和一样) 
            //   2.1 不匹配 返回false，即前面字符已经匹配，但s多出了当前字母，所以整串不匹配
            //   2.2 匹配 看 dp[i-1][j] 即*前字母可以重复出现 再加一个重复字母也匹配 整串=dp[i-1][j]
            if (p[j - 1] === "*") {
                dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (s[i - 1] === p[j - 2] || p[j - 2] === '.'))
            } else if (s[i - 1] === p[j - 1] || p[j - 1] === ".") {
                // 如果当前s 和当前p 匹配(包括.和一样) 
                // 整串 = dp[i - 1][j - 1] 即看前面的字串是否匹配
                dp[i][j] = dp[i - 1][j - 1]
            } else {
                // 如果当前s 和当前p 那么当前字串一定不匹配
                dp[i][j] = false
            }

        }
    }
    // console.log(dp);
    return dp[sn - 1][pn - 1]
};
// @lc code=end

console.log(isMatch("mississippi", "mis*is*p*."));